package me.shan.data.structure;

import lombok.Data;

import java.util.ArrayList;
import java.util.List;
import me.shan.util.RandomUtils;

/**
 * 描述：单链表
 *
 * @author liuchuang
 * @date 2021/6/16
 */
public class LinkedList<T> {

    private Node<T> node;

    public LinkedList(T value) {
        this.node = new Node<>(value);
    }

    public LinkedList(){

    }

    public void add(T value) {
        if (node == null) {
            node = new Node<>(value);
        } else {
            Node<T> pre = node;
            Node<T> now = pre.getNext();
            while (now != null) {
                pre = now;
                now = pre.getNext();
            }
            pre.setNext(new Node<>(value));
        }
    }

    /**
     * 反转链表
     * 原始链表：1 -> 2 -> 3 -> 4
     * 反转之后：4 -> 3 -> 2 -> 1
     */
    public void revers() {
        if (node == null || node.getNext() == null) {
            return;
        }
        Node<T> pre = null;
        Node<T> now = node;
        Node<T> temp;
        while (now != null) {
            // 保留
            temp = now.getNext();
            now.setNext(pre);
            pre = now;
            now = temp;
        }
        // 一定要设置链表头指针
        node = pre;
    }

    public void delete(T value) {
        if (node == null) {
            return;
        }
        while (node != null && node.getValue() == value) {
            node = node.getNext();
        }
        if (node == null) {
            return;
        }
        Node<T> now = node;
        Node<T> pre = null;
        while (now != null) {
            if (now.getValue() != value) {
                pre = now;
                now = now.getNext();
            } else {
                pre.setNext(now.getNext());
                now.setNext(null);
                now = pre.getNext();
            }
        }
    }

    public List<T> getList() {
        List<T> list = new ArrayList<>();
        Node<T> current = node;
        while (current != null) {
            list.add(current.getValue());
            current = current.getNext();
        }
        return list;
    }

    /**
     * 随机链表生成器
     * @param maxLen 最大长度 [1, maxLen]
     * @param maxValue 最大值的范围 [-maxValue, maxValue]
     * @return 返回生成的链表
     */
    public static LinkedList<Integer> getRandomLinkedList (int maxLen, int maxValue) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        // 生成的长度为[1, maxLen]
        int length = RandomUtils.getRandomLen(maxLen);
        int count = 0;
        while (count < length) {
            linkedList.add(RandomUtils.getRandomValue(maxValue));
            count++;
        }
        return linkedList;
    }



    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList{ ");
        Node<T> next = null;
        if (node != null) {
            sb.append(node.getValue());
            next = node.getNext();
        }
        while (next != null) {
            sb.append(" -> ").append(next.getValue());
            next = next.getNext();
        }
        // 追加一个尾指针空
        if (node != null) {
            sb.append(" -> ");
        }
        sb.append("null");
        sb.append(" }");
        return sb.toString();
    }

    public static void main(String[] args) {
        int maxLen = 200;
        int maxValue = 10000;
        int times = 10000;
        System.out.println("开始执行");
        while (times > 0) {
            // 生成链表
            LinkedList<Integer> linkedList = getRandomLinkedList(maxLen, maxValue);
            // 拷贝一份链表对应的数组
            List<Integer> list = linkedList.getList();
            linkedList.revers();
            if (checkFail(linkedList, list)) {
                System.out.println("失败，赶紧改bug，骚年");
                System.out.println(list);
                System.out.println(linkedList);
            }
            times--;
        }
        System.out.println("执行结束");
    }

    /**
     * 是否校验不通过
     * @param linkedList 反转后的链表
     * @param list 原始数组
     * @return 是否不通过，不匹配返回true
     */
    private static boolean checkFail(LinkedList<Integer> linkedList, List<Integer> list) {
        int length = list.size();
        Node<Integer> node = linkedList.node;
        int index = length - 1;
        while (index > 0) {
            if (!list.get(index).equals(node.getValue())) {
                return true;
            }
            index--;
            node = node.getNext();
        }

        return false;
    }

}

@Data
class Node <T> {
    private T value;

    private Node<T> next;

    public Node (T value) {
        this.value = value;
    }

}
